#include<bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define pb push_back
#define lowbit(x) (x&(-x))
#define m_p make_pair
#define P pair<int,int>
typedef long long ll;
const ll MX=1e18;
ll t[800005],tg[800005];
void build(int p,int l,int r){
    t[p]=-MX;tg[p]=0;
    if(l==r) return;
    int mid=((l+r)>>1);
    build(p*2,l,mid);build(p*2+1,mid+1,r);
}
void go(int p,ll v){
    t[p]+=v;
    tg[p]+=v;
}
void pushdown(int p){
    go(p*2,tg[p]);go(p*2+1,tg[p]);
    tg[p]=0;
}
void upd(int p,int l,int r,int L,int R,ll v){
    //cout<<p<<" "<<l<<" "<<r<<endl;
    if(L<=l&&r<=R){
        go(p,v);
        return;
    }
    pushdown(p);
    int mid=((l+r)>>1);
    if(L<=mid) upd(p*2,l,mid,L,R,v);
    if(R>mid) upd(p*2+1,mid+1,r,L,R,v);
    t[p]=max(t[p*2],t[p*2+1]);
}
ll query(int p,int l,int r,int L,int R){
    //cout<<p<<" "<<l<<" "<<r<<endl;
    if(L<=l&&r<=R) return t[p];
    pushdown(p);
    ll ans=-MX;
    int mid=((l+r)>>1);
    if(L<=mid) ans=max(ans,query(p*2,l,mid,L,R));
    if(R>mid) ans=max(ans,query(p*2+1,mid+1,r,L,R));
    return ans;
}
int a[200005];
int id[200005];
int in[200005];
ll dp[200005];
int atl[1000005],atr[1000005];
P tmp[200005];
void solve(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        tmp[i]=m_p(a[i],i);
    }
    a[n]=0;tmp[n]=m_p(0,n);
    n++;
    for(int i=0;i<n;i++){
        atl[a[i]]=n+2;
        atr[a[i]]=-1;
    }
    sort(tmp,tmp+n);
    for(int i=0;i<n;i++){
        in[tmp[i].sc]=i;
        if(atl[tmp[i].fr]==n+2) atl[tmp[i].fr]=i;
        atr[tmp[i].fr]=i;
    }
    build(1,0,n-1);
    ll add=0;
    for(int i=0;i<n;i++){
        if(i&&a[i]==a[i-1]){
            upd(1,0,n-1,0,n-1,a[i]);
            add+=a[i];
            upd(1,0,n-1,in[i-1],in[i-1],-a[i]);
        }
        ll ans=0;
        int p1=atl[a[i+1]];
        int p2=atr[a[i+1]];
        ans=max(ans,query(1,0,n-1,0,n-1));
        ans=max(ans,query(1,0,n-1,p1,p2)+a[i+1]);
        dp[i]=ans;
        upd(1,0,n-1,in[i],in[i],dp[i]+MX-add);
    }
    cout<<dp[n-2]<<endl;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int t;cin>>t;
    while(t--) solve();
    return 0;
}